package com.zhugang.week03;

import java.util.Stack;

/**
 * @program algorithms
 * @description: stackSequeces
 * @author: chanzhugang
 * @create: 2022/06/14 09:23
 */
public class StackSequences2 {

    public static void main(String[] args) {
        StackSequences2 stackSequences2 = new StackSequences2();
        int[] pushed = new int[]{1, 2, 3, 4, 5};
        int[] poped = new int[]{4, 3, 5, 2, 1};
        boolean res = stackSequences2.validateStackSequences(pushed, poped);
        System.out.println(res);
    }

    /**
     * 剑指offer31. 栈的压入、弹出序列
     *
     * @param pushed
     * @param poped
     * @return
     */
    public boolean validateStackSequences(int[] pushed, int[] poped) {
        /**
         * 定义角标i，j，先出栈（满足条件）；后入栈
         */
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        int j = 0;
        int k = 0;
        while (k < pushed.length + poped.length) {
            k++;
            if (!stack.isEmpty() && j < poped.length && stack.peek() == poped[j]) {
                stack.pop();
                j++;
                continue;
            }
            if (i < pushed.length) {
                stack.push(pushed[i]);
                i++;
                continue;
            }
            return false;
        }
        return true;
    }

}